package com.dyz.leetcode;

public class CanPartition416 {
    //动态规划
    public boolean canPartition(int[] nums) {
        int sum =0;
        for (int num : nums){
            sum+=num;
        }
        if (sum%2!=0){return false;}

        int target = sum /2;
        boolean[] dp = new boolean[target+1];
        dp[0]=true;
        //0-1背包问题， 一个物品只能使用一次
        for(int num :nums){
            //先从后向前，先计算dp[i]在计算dp[i-num]
            for(int j=target; j>=num;--j){
                dp[j] = dp[j]||dp[j-num];
            }
        }
        return dp[target];
    }
}
